package wei.xinya.sort;

public class QuickSort {
    private static int count = 0;

    public static void main(String[] args) {
        int[] num = {45, 78, 14, 52, 11, 64, 55, 99, 17, 18};

        quickSort(num, 0, num.length - 1);
        System.out.println("数组个数：" + num.length);
        System.out.println("循环次数：" + count);
    }

    private static void quickSort(int[] num, int left, int right) {
        // 打印
        System.out.println(arrayToString(num, "左标：" + left + "--右标：" + right));
        // 如果left等于right，即数组只有一个元素，直接返回
        if (left >= right) {
            return;
        }
        // 设置最左边的元素为基准值
        int key = num[left];
        // 数组中比key小的放在左边，比key大的放在右边，key值下标为i
        int i = left;
        int j = right;
        while (i < j) {
            // j向左移，直到遇到比key小的值
            while (num[j] >= key && i < j) {
                j--;
            }
            // i向右移，直到遇到比key大的值
            while (num[i] <= key && i < j) {
                i++;
            }
            // i和j指向的元素交换
            if (i < j) {
                int temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
        num[left] = num[i];
        num[i] = key;
        count++;
        quickSort(num, left, i - 1);
        quickSort(num, i + 1, right);
    }

    private static String arrayToString(int[] arr, String flag) {
        StringBuilder str = new StringBuilder("数组为(" + flag + ")：");
        for (int a : arr) {
            str.append(a).append(" ");
        }
        return str.toString();
    }
}
